1. Field of the Invention
This invention relates generally to document replication systems and more particularly to a method and apparatus for segmenting and enhancing compound documents for image replication applications.
2. Description of the Related Art
The quest for high quality in everyday copying applications has led to increased sophistication in scanners and printers. In particular, the desire for high quality text and graphics output has forced modern scanners and printers to operate at 600 dots per inch (dpi) or higher dpi resolutions even on basic document applications. However, the associated increases in the costs of these devices leaves little room for the expense of signal processing algorithms which must still accomplish high quality output in an automated mode of operation. The result is a direct need for compound document processing techniques of very low computational and memory complexity.
The constraint for very low cost algorithms is in part alleviated by the high resolution devices that make up a copier. Modem scanners with low noise sensors and printers with precision dot placement no longer necessitate very high performance signal processing for noise removal, deblurring, etc. However, halftone dots in the input become much more pronounced in high resolutions, thereby resulting in possible Moiré artifacts that are introduced if such regions are printed unprocessed. FIGS. 1A–1C illustrate various portions of a document scanned at different resolutions. FIG. 1A is scanned at 150 dpi, FIG. 1B is scanned at 300 dpi and FIG. 1C is scanned at 600 dpi. It should be appreciated that FIG. 1A and FIG. 1B were scaled to 600 dpi by pixel replication for comparison purposes. As illustrated in successive halftone regions 102a–102c of FIGS. 1A–1C, respectively, the resolution increases from 150 dpi to 600 dpi. While the text and other edges become sharper with the increasing resolution, the halftone dots become more pronounced.
Attempts to segment a compound document to halftone and non-halftone regions have met with limited success. For example, some techniques require pre-segmentation of the document into blocks or other rectangular regions. Additionally, some segmentation techniques look at the document at a single resolution, which inevitably leads to erroneous decisions and may restrict the technique to detecting a particular class of halftones. Furthermore, these techniques are not applicable to general document types, such as scanned documents, and are associated with a high computational complexity and excessive consumption of memory resources.
Additionally, previous attempts mainly concentrate on region classification on documents that have been pre-segmented to their constituent regions. Each one of the pre-segmented regions are classified into various classes and the segmentation is typically delegated to sophisticated and computationally complex document analysis algorithms. Furthermore, irrespective of how simple the region classification is, such approaches demand at least two passes on the data resulting in significant memory and memory-bandwidth requirements. Moreover, the overall operation of pre-segmentation and classification may still require considerable computation. These pre-segmentation requiring methods range from simple techniques which use an “α-crossing” technique for detecting halftone regions, and techniques which operate on binary only documents and detect halftone regions using predefined masks, to the more elaborate and computationally complex techniques, which utilize Fourier transforms and tuned directional bandpass filters for texture analysis and halftone detection. The previous techniques effectively pit halftone and text regions against one another by basing the identification decision on complex statistics (the alternative hypothesis are text, halftone, non-halftone, etc.) By subtracting most of the influence of real document edges, the segmentation and identification decisions in this work are based on simple statistics (the alternative hypothesis are halftone and non-halftone).
Other work that tries to identify halftones by detecting periodicities is limited to input documents containing certain types of halftones. Moreover, one must be assured that periodicities in the original halftone are sufficiently preserved after the color space change due to the scan of the original printed halftone (for e.g., CMYK to RGB). Techniques that try to detect real document edges that are not due to halftone dots by using edge continuity analysis are severely sensitive to thresholds since disconnected halftone dots may appear connected depending on the threshold used in edge detection.
As a result, there is a need to solve the problems of the prior art to provide a technique that segments a document irrespective of the document characteristics and minimizes the computational cost as well as memory consumption.